home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Interactive Reference Guide / C-C++ Interactive Reference Guide.iso / c_ref / csource4 / 246_01 / cycle41.c < prev    next >
Text File  |  1987-10-29  |  4KB  |  178 lines
  1.  
  2.  
  3. /* CYCLE41.C                     */
  4. /* program to analyze the cycles of a cellular   */
  5. /* automaton and report all the periodic states. */
  6. /* [Harold V. McIntosh, 21 May 1987]         */
  7.  
  8. # include <stdio.h>
  9.  
  10. # define KK     4            /* number of states/cell    */
  11. # define NS     10            /* number of distinct sums    */
  12. # define NW    24            /* pause after so many lines    */
  13.  
  14. int  arr1[16], arr2[16];
  15. unsigned int arry[16384];
  16. int  binrule[KK][KK][KK], rule[NS];
  17. int  cy, cp, mc, nc, nl;
  18.  
  19. main() {
  20. int  i;
  21.  
  22. printf("Rule number:\n\n");
  23. printf("0..1..2..3\n");
  24. for (i=0; i<NS; i++) rule[i]=kbdin()-'0';
  25. printf("\n");
  26.  
  27. totobin();
  28.  
  29. nc=0;
  30. nl=0;
  31. /* cp=KK^cy; */
  32. /* cp=4^5; */
  33.  
  34. printf("Cycles of length 4"); kwait(0);
  35.  mc=7;
  36.  cy=4;
  37.  cp=256;
  38.  pass1();
  39.  pass2();
  40.  pass4();
  41.  
  42. printf("Cycles of length 5"); kwait(0);
  43.  mc=6;
  44.  cy=5;
  45.  cp=1024;
  46.  pass1();
  47.  pass2();
  48.  pass4();
  49.  
  50. printf("Cycles of length 6"); kwait(0);
  51.  mc=5;
  52.  cy=6;
  53.  cp=4096;
  54.  pass1();
  55.  pass2();
  56.  pass4();
  57.  
  58. printf("Cycles of length 7"); kwait(0);
  59.  mc=4;
  60.  cy=7;
  61.  cp=16384;
  62.  pass1();
  63.  pass2();
  64.  pass4();
  65.  
  66. } /* end main */
  67.  
  68. /* Pass 1 makes arry[i] equal to the successor of i */
  69.  
  70. pass1() {int i, j, x;
  71.   printf(" Pass1\015");
  72.   for (j=0; j<cp; j++) {
  73.     x=j; for (i=0; i<cy; i++) {arr1[cy-i-1]=x%KK; x/=KK;};
  74.     evolve(cy);
  75.     x=0; for (i=0; i<cy; i++) x=KK*x+arr2[i]; arry[j]=x;
  76.   }; }
  77.  
  78. /* calculate one generation of evolution in a ring of length n */
  79.  
  80. evolve(n) int n; {
  81. int i;
  82.   arr2[0]=binrule[arr1[n-1]][arr1[0]][arr1[1]];
  83.   for (i=1; i<n-1; i++) arr2[i]=binrule[arr1[i-1]][arr1[i]][arr1[i+1]];
  84.   arr2[n-1]=binrule[arr1[n-2]][arr1[n-1]][arr1[0]];
  85. }
  86.  
  87. /* Pass 2 flags all links with an incoming arrow */
  88.  
  89. pass2() {int j, m, x;
  90. printf(" Pass2\015");
  91. do {
  92. m=0;
  93. for (j=0; j<cp; j++) arry[j]|=0x8000;
  94. for (j=0; j<cp; j++) {x=arry[j];
  95.  if (x!=0xFFFF) arry[x&0x7FFF]&=0x7FFF;};
  96. for (j=0; j<cp; j++) {
  97.  if ((arry[j]>0x7FFF) && (arry[j]!=0xFFFF)) {arry[j]=0xFFFF; m=1;};};
  98.  } while (m!=0);
  99. }
  100.  
  101. /* pass4 - print loops which remain */
  102.  
  103. pass4() {
  104. int j, x, y, m;
  105. printf(" pass4 \015");
  106. for (j=0; j<cp; j++) {
  107.  x=j; y=arry[j]; arry[j]=0xFFFF; m=0;
  108.  while (y!=0xFFFF) {prf(x,y); x=y; y=arry[x]; arry[x]=0xFFFF; m=1;};
  109.  if (m==1) kwait(0);
  110.  };
  111. }
  112.  
  113. /* change totalistic rule to general rule */
  114.  
  115. totobin() {
  116. int i0, i1, i2;
  117. for (i0=0; i0<KK; i0++) {
  118. for (i1=0; i1<KK; i1++) {
  119. for (i2=0; i2<KK; i2++) {
  120. binrule[i0][i1][i2]=rule[i0+i1+i2];
  121. };};};
  122. }
  123.  
  124. /* print the link */
  125.  
  126. prf(j,x) int j, x; {int i, y;
  127.   kwait(1);
  128.   y=j; for (i=0; i<cy; i++) {arr1[i]=y%KK; y/=KK;};
  129.   for (i=0; i<cy; i++) printf("%1d",arr1[i]);
  130.   printf("-");
  131.   y=x; for (i=0; i<cy; i++) {arr1[i]=y%KK; y/=KK;};
  132.   for (i=0; i<cy; i++) printf("%1d",arr1[i]);
  133.   printf("  ");
  134. }
  135.  
  136. /* print arry - for diagnostic purposes */
  137. pall() {int j;
  138. for (j=0; j<cp; j++) printf("%4d",arry[j]);
  139. }
  140.  
  141. /* print cycle - for diagnostic purposes */
  142. pcy() {int j;
  143. for (j=0; j<cy; j++) printf("%1d",arr2[j]);
  144. }
  145.  
  146. /* limit j to interval (i,k) */
  147. int lim(i,j,k) int i, j, k;
  148.     {if (i>=j) return i; if (k<=j) return k; return j;}
  149.  
  150. /* keyboard status */
  151. kbdst() {return bdos(11)&0xFF;}
  152.  
  153. /* direct keyboard input, no echo */
  154. kbdin() {int c;
  155. if ((c=bdos(7)&0xFF)=='\0') c=(bdos(7)&0xFF)|0x80;
  156. videoputc(c,1);
  157. return c;}
  158.  
  159. /* pause at the end of a full screen */
  160. /* kwait(0) - <cr><lf> and count it  */
  161. /* kwait(1) - count columns          */
  162.  
  163. kwait(i) int i; {
  164. switch (i) {
  165.   case 0: printf("\n"); nc=0; nl++; break;
  166.   case 1: if (nc==mc) {printf("&\n"); nc=1; nl++;} else nc++; break;
  167.   default: break;};
  168. if (nl==NW) {
  169.   nl=0;
  170.   printf(" press any key to continue\015");
  171.   while (kbdst()) {};
  172.   kbdin();
  173.   printf("-                         \n");
  174.   };
  175. }
  176.  
  177. /* end */
  178.